/*
 * @lc app=leetcode.cn id=861 lang=java
 *
 * [861] 翻转矩阵后的得分
 */

// @lc code=start
class Solution {
    /**
方法一：贪心

根据题意，能够知道一个重要的事实：给定一个翻转方案，则它们之间任意交换顺序后，得到的结果保持不变。
因此，我们总可以先考虑所有的行翻转，再考虑所有的列翻转。
不难发现一点：为了得到最高的分数，矩阵的每一行的最左边的数都必须为 111。
为了做到这一点，我们可以翻转那些最左边的数不为 111 的那些行，而其他的行则保持不动。
当将每一行的最左边的数都变为 111 之后，就只能进行列翻转了。
为了使得总得分最大，我们要让每个列中 111 的数目尽可能多。
因此，我们扫描除了最左边的列以外的每一列，如果该列 000 的数目多于 111 的数目，就翻转该列，其他的列则保持不变。

然而不需要实际去翻转这个矩阵，直接计算即可。
注意考虑最初进行的行反转。
     */
    public int matrixScore(int[][] A) {
        // 默认行翻转后第0列全是1
        int m=A.length,n=A[0].length;//m行,n列
        int ans = m*(1<<(n-1));//直接做左移运算即是乘2，由于行反转，第一列全是1
        for(int i = 1;i<n;i++){//第0列已经计算过了,从第一列开始算
            int t=0;
            for(int j=0;j<m;j++){//从第0行算起
                //这里要考虑最初进行的行反转，如果第一列的值为0，说明进行了行反转
                if(A[j][0] == 1) t+= A[j][i];
                else t+=1-A[j][i];//进行了行反转，则该元素的实际取值为 1-A[j][i],这一点比较有趣。
            }
            int c = Math.max(t, m-t);
            ans+= c*(1<<(n-i-1));
        }
        return ans;
    }
}
// @lc code=end

